package com.longge;

/**
 * @program: my-code
 * @description:
 * @author: longge
 * @create: 2021-05-06 01:59
 */
public class CountArrangement {

    int count = 0;

    public int countArrangement(int n) {

        boolean[] visited = new boolean[n + 1];
        backtrack(n, visited, 1);
        return count;
    }

    private void backtrack(int n, boolean[] visited, int index) {

        if (index > n) {
            count++;
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (visited[i]) continue;
            if (index % i != 0 && i % index != 0) continue;
            visited[i] = true;
            backtrack(n, visited, index + 1);
            visited[i] = false;
        }
    }
}
